/*!
 Temelia - Trie tree implementation source file.

 Copyright (C) 2008, 2009 Ceata (http://ceata.org/proiecte/temelia).

 @author Dascalu Laurentiu

 This program is free software; you can redistribute it and
 modify it under the terms of the GNU General Public License
 as published by the Free Software Foundation; either version 3
 of the License, or (at your option) any later version.

 This program is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU General Public License for more details.

 You should have received a copy of the GNU General Public License
 along with this program; if not, write to the Free Software
 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
 */

#include <string.h>
#include "include/trie_tree.h"
#include "include/queue.h"

#define SYMBOLS_NUMBER	('z' - 'a' + 1)

static trie_tree_t _trie_search(trie_tree_t trie, char *suffix);
static void _trie_delete_node(trie_tree_t trie);

struct _trie_tree_t
{
	/*! user's key stored in current node */
	void *key;

	/*! reference to parent */
	struct _trie_tree_t *parent;

	/*! references to children */
	vector_t children;
};

trie_tree_t trie_new(void *key)
{
	int i;
	trie_tree_t trie;

	trie = (struct _trie_tree_t *) _new(sizeof(struct _trie_tree_t));
	trie->key = key;
	trie->parent = NULL;
	trie->children = vector_new(SYMBOLS_NUMBER);
	for (i = 0; i < SYMBOLS_NUMBER; i++)
		vector_push_back(trie->children, NULL);

	return trie;
}

void trie_delete(trie_tree_t trie)
{
	int i, n;

	_ASSERT(trie, ==, NULL, INVALID_INPUT,);

	n = vector_get_size(trie->children);

	if (n == 0)
	{
		_trie_delete_node(trie);
		return;
	}

	for (i = 0; i < n; i++)
		trie_delete(vector_get_key_at(trie->children, i));
	vector_delete(trie->children);
	_delete(trie);
}

void *trie_get_key(trie_tree_t trie)
{
	_ASSERT(trie, ==, NULL, NULL_POINTER, NULL);

	return trie->key;
}

trie_tree_t trie_get_parent(trie_tree_t trie)
{
	_ASSERT(trie, ==, NULL, NULL_POINTER, NULL);

	return trie->parent;
}

void *trie_get_children(trie_tree_t trie)
{
	_ASSERT(trie, ==, NULL, INVALID_INPUT, NULL);

	return trie->children;
}

int trie_get_children_number(trie_tree_t trie)
{
	_ASSERT(trie, ==, NULL, INVALID_INPUT, -1);

	return vector_get_size(trie->children) % 256;
}

trie_tree_t trie_get_child(trie_tree_t trie, int index)
{
	_ASSERT(trie, ==, NULL, INVALID_INPUT, NULL);
	_ASSERT(index, <, 0, INVALID_INPUT, NULL);
	_ASSERT(index, >=, SYMBOLS_NUMBER, INVALID_INPUT, NULL);

	return vector_get_key_at(trie->children, index);
}

trie_tree_t trie_insert(trie_tree_t _trie, char *suffix, void *key)
{
	trie_tree_t add = NULL, next_trie;
	int nints, index;

	_ASSERT(suffix, ==, NULL, NULL_POINTER, NULL);

	nints = strlen(suffix);

	_ASSERT(nints, <, 1, INVALID_INPUT, NULL);

	// Input should be formed from intacters 'a'-'z'.
	_ASSERT(suffix[0], <, 'a', INVALID_INPUT, NULL);
	_ASSERT(suffix[0], >, 'z', INVALID_INPUT, NULL);

	index = suffix[0] - 'a';
	next_trie = vector_get_key_at(_trie->children, index);

	if (nints == 1)
	{
		if (next_trie != NULL)
		{
			next_trie->key = key;
			return next_trie;
		}
		else
		{
			add = trie_new(NULL);
			add->parent = _trie;
			vector_set_key_at(_trie->children, index, add);
			add->key = key;
			return add;
		}
	}
	else
	{
		if (next_trie != NULL)
			return trie_insert(next_trie, suffix + 1, key);
		else
		{
			add = trie_new(NULL);
			add->parent = _trie;
			vector_set_key_at(_trie->children, index, add);
			return trie_insert(add, suffix + 1, key);
		}
	}
}

void *trie_search(trie_tree_t trie, char *suffix)
{
	return trie_get_key(_trie_search(trie, suffix));
}

void trie_remove(trie_tree_t _trie, char *suffix)
{
	int i;
	trie_tree_t trie_removed = _trie_search(_trie, suffix), aux;

	_ASSERT(trie_removed, ==, NULL, NULL_POINTER,);

	/*
	 * Remove a node only if it's parent isn't NULL, it's parent holds a NULL key
	 * and it has no children.
	 */
	while (1)
	{
		aux = trie_removed;
		trie_removed = trie_removed->parent;

		if (trie_get_children_number(aux) > 0)
		{
			aux->key = NULL;
			break;
		}

		if (trie_removed)
		{
			for (i = 0; i < SYMBOLS_NUMBER; i++)
				if (vector_get_key_at(trie_removed->children, i) == aux)
				{
					vector_set_key_at(trie_removed->children, i, NULL);
					break;
				}
		}

		_trie_delete_node(aux);

		if (!trie_removed || trie_removed->key)
			break;
	}
}

int trie_children_number(trie_tree_t trie)
{
	int i = 0, children = 0;

	_ASSERT(trie, ==, NULL, NULL_POINTER, -1);

	for (; i < SYMBOLS_NUMBER; i++)
		if (vector_get_key_at(trie->children, i))
			++children;
	return children;
}

int trie_is_leaf(trie_tree_t trie)
{
	_ASSERT(trie, ==, NULL, NULL_POINTER, -1);

	return trie_children_number(trie) == 0;
}

int trie_is_empty(trie_tree_t trie)
{
	_ASSERT(trie, ==, NULL, INVALID_INPUT, -1);

	return trie->parent == NULL && trie_is_leaf(trie);
}

void trie_preorder(trie_tree_t trie, void key_handler(void *key, void *context), void *context)
{
	int i;

	_ASSERT(trie, ==, NULL, NULL_POINTER,);
	_ASSERT(key_handler, ==, NULL, NULL_POINTER,);

	if (trie->key)
		key_handler(trie->key, context);

	for (i = 0; i < SYMBOLS_NUMBER; i++)
		trie_preorder(vector_get_key_at(trie->children, i), key_handler,
				context);
}

void trie_postorder(trie_tree_t trie, void key_handler(void *key, void *context), void *context)
{
	int i;

	_ASSERT(trie, ==, NULL, NULL_POINTER,);
	_ASSERT(key_handler, ==, NULL, NULL_POINTER,);

	for (i = SYMBOLS_NUMBER - 1; i >= 0; i--)
		trie_postorder(vector_get_key_at(trie->children, i), key_handler,
				context);

	if (trie->key)
		key_handler(trie->key, context);
}

void trie_level_order(trie_tree_t trie, void key_handler(void *key, void *context),
		void *context)
{
	int i;
	queue_t queue;

	queue = queue_new(DEFAULT_SIZE);
	queue_push_back(queue, trie);

	while (!queue_is_empty(queue))
	{
		trie = queue_get_front(queue);
		queue_pop_front(queue);

		if (trie->key)
			key_handler(trie->key, context);

		for (i = 0; i < SYMBOLS_NUMBER; i++)
			if (vector_get_key_at(trie->children, i))
				queue_push_back(queue, vector_get_key_at(trie->children, i));
	}

	queue_delete(queue);
}

static trie_tree_t _trie_search(trie_tree_t trie, char *suffix)
{
	int index;

	_ASSERT(trie, ==, NULL, NULL_POINTER, NULL);
	_ASSERT(suffix, ==, NULL, NULL_POINTER, NULL);

	if (suffix[0] == '\0')
		return trie;

	index = suffix[0] - 'a';
	return _trie_search(vector_get_key_at(trie->children, index), suffix + 1);
}

static void _trie_delete_node(trie_tree_t trie)
{
	_ASSERT(trie, ==, NULL, NULL_POINTER,);

	vector_delete(trie->children);
	_delete(trie);
}
